/**
 *  Selection Sort
 *
 *  Time complexity:
 *  Space complexity:
 */

import java.util.Arrays;

class SelectionSort<E extends Comparable<E>> {

    public void sort(E[] a) {
        int N = a.length;

        for (int i = 0; i < N - 1; i++) { // Outter loop, go through from left to right
            int min_index = i;
            for (int j = i + 1; j < N; j++) { // Inner loop, find the smallest item
                if (a[j].compareTo(a[min_index]) < 0) {
                    min_index = j;
                }
            }
            // Finally, replace the smallest item with a[i]
            if (i != min_index) {
                swap(a, i, min_index);
            }
        }
    }

    private void swap(E[] a, int i, int j) {
        E tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

}
